// 归并排序，
// 背景当我们有两个已经有顺序的数组时，我们想合并成一个新的有顺序的数组
// 下面这个排序方法的时间复杂度我们可以通过master公式来计算
// 通过公式可以计算出时间复杂度T(N) = 2*T(N/2)+O(N^1)的时间复杂度其中abc分别为221所以满足=的情况我们可以计算出时间复杂度为O(N*logN)
const process = (arr: Array<number>,L:number,R:number) =>{
    if(L == R) return
    let mid = L + ((R-L) >>1)
    process(arr,L,mid)
    process(arr,mid+1,R)
    merge(arr,L,mid,R)
}
const merge = (arr:Array<number>,L:number,M:number,R:number) =>{
    let help:Array<number> = []
    let i = 0
    let p1 = L
    let p2 = M+1
    while (p1 <= M && p2 <= R){
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] :arr[p2++]
    }
    while(p1 <= M){
        help[i++] = arr[p1++]
    }
    while(p2 <= R){
        help[i++] = arr[p2++]
    }
    for(i = 0; i < help.length; i++){
        arr[L+i] = help[i]
    }
}
let arr = [1,2,4,3,9,6,5,7,0]
process(arr,0,arr.length-1)
console.log(arr)
export default process
